package com.hqq.exercise.tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * TreeNodeUtil
 * Created by heqianqian on 2017/8/30.
 */
public class TreeNodeUtil {

    /**
     * @param array array of tree node
     */
    public static TreeNode array2AVL(int[] array) {
        TreeNode root = new TreeNode(array[0]);
        TreeNode head = root;
        for (int i = 1; i < array.length; i++) {
            TreeNode temp = new TreeNode(array[i]);
            if (array[i] > root.val) {
                root.right = temp;
            } else {
                root.left = temp;
            }
            root = temp;
        }
        return head;
    }

    /**
     * @param array int array
     * @return root of binary tree
     */
    public static TreeNode arrayToTree(int[] array) {
        TreeNode[] nodes = new TreeNode[array.length];
        for (int i = 0; i < array.length; i++) {
            nodes[i] = new TreeNode(array[i]);
        }
        for (int i = 0; i < array.length / 2 - 1; i++) {
            nodes[i].left = nodes[2 * i + 1];
            nodes[i].right = nodes[2 * i + 2];
            System.out.println(nodes[i].val + " left = " + nodes[2 * i + 1].val);
            System.out.println(nodes[i].val + " right = " + nodes[2 * i + 2].val);
        }
        return nodes[0];
    }

    /**
     * @param root root of binary tree
     */
    public static void preOrderTraversal(TreeNode root) {
        System.out.println(root.val);
        if (root.left != null) {
            preOrderTraversal(root.left);
        }
        if (root.right != null) {
            preOrderTraversal(root.right);
        }
    }

    /**
     * @param root root of binary tree
     * @return list of tree nodes
     */
    public static List<Integer> preOrderTraversalList(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        return list;
    }

    public static void levelTraversal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedBlockingQueue<>();
        if (root == null) {//如果二叉树为空
            return;
        }
        while (root != null) {
            System.out.print(root.val + " ");
            if (root.left != null) {
                queue.add(root.left);
            }
            if (root.right != null) {
                queue.add(root.right);
            }
            root = queue.poll();
        }
    }
}
